from bisect import bisect_right, bisect_left
from collections import defaultdict
from typing import List


class RangeFreqQuery:
    defaultdict(list)
    # 创建的字典，在访问不存在的键时会自动初始化空列表，从而简化了 “键 - 列表值” 类型的数据处理逻辑，避免了
    # KeyError
    # 错误，让代码更简洁高效。使用前需通过
    # from collections import defaultdict
    # 导入
    def __init__(self, arr: List[int]):
        pos = defaultdict(list)
        for i,x in enumerate(arr):
            pos[x].append(i)
        self.pos = pos
    def query(self, left: int, right: int, value: int) -> int:
        a = self.pos[value]
        return bisect_right(a,right)-bisect_left(a,left)

# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)